/**
 * 面试题26：树的子结构
 */
public class Offer_26 {
    /**
     * 递归
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 约定空树不是任意一个树的子结构
        if (A == null || B == null) {
            return false;
        }
        // 先从根节点判断 B 是不是 A 的子结构，如果不是在分别从左右两个子树判断，
        // 只要有一个为 true，就说明 B 是 A 的子结构
        return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    private boolean recur(TreeNode A, TreeNode B) {
        // 如果 B 为空，说明已访问完，B 是 A 的子结构
        if (B == null) {
            return true;
        }
        // 如果 B 不为空但 A 为空，或者二者节点值不同，则 B 不是 A 的子结构
        if (A == null || A.val != B.val) {
            return false;
        }
        // 当前节点相同，递归比较二者的左右子树
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}
